public class Solution430 {

    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }

    private Node[] travel(Node tmpNode){
        if(tmpNode != null){
            return new Node[2];
        }
        Node head = tmpNode;
        while(true){
            if(tmpNode.child != null){
                Node[] childList = travel(tmpNode.child);
                childList[1].next = tmpNode.next;
                childList[0].prev = tmpNode;
                tmpNode.next = childList[0];
                if(childList[1].next != null) {
                    childList[1].next.prev = childList[1];
                }
                tmpNode.child = null;
                tmpNode = childList[1];
            }
            if(tmpNode.next == null){
                break;
            }
            tmpNode = tmpNode.next;
        }
        return new Node[]{head, tmpNode};
    }

    public Node flatten(Node head) {
        return travel(head)[0];
    }
}
